#include<iostream>
#include<vector> 
using namespace std;
  template <typename Comparable>
  void SORT( vector<Comparable> & items )
  {
     if( items.size( ) > 1 )
     {
         vector<Comparable> smaller;
         vector<Comparable> same;
         vector<Comparable> larger;
 
         auto chosenItem = items[ items.size( ) / 2 ];
  
         for( auto & i : items )
         {
              if( i < chosenItem )
                   smaller.push_back( std::move( i ) );
              else if( chosenItem < i )
                   larger.push_back( std::move( i ) );
              else
                   same.push_back( std::move( i ) );
         }
  
         SORT( smaller ); 
         SORT( larger ); 
  
         std::move( begin( smaller ), end( smaller ), begin( items ) );
         std::move( begin( same ), end( same ), begin( items ) + smaller.size( ) );
         std::move( begin( larger ), end( larger ), end( items ) - larger.size( ) );
     }
  }
  
  template <typename Comparable>
  void quicksort1( vector<Comparable> & a )
  {
     quicksort1( a, 0, a.size( ) - 1 );
  }
  
  template <typename Comparable>
  void quicksort2( vector<Comparable> & a )
  {
     quicksort2( a, 0, a.size( ) - 1 );
  }
  
  template <typename Comparable>
  const Comparable & median3( vector<Comparable> & a, int left, int right )
  {
      int center = ( left + right ) / 2;
 
      if( a[ center ] < a[ left ] )
         std::swap( a[ left ], a[ center ] );
      if( a[ right ] < a[ left ] )
         std::swap( a[ left ], a[ right ] );
      if( a[ right ] < a[ center ] )
         std::swap( a[ center ], a[ right ] );
  
      std::swap( a[ center ], a[ right - 1 ] );
  }
  
  template <typename Comparable>
  void quicksort1( vector<Comparable> & a, int left, int right )
  {
      if( left + 10 <= right )
      {
          const Comparable & pivot = median3( a, left, right );
  
          int i = left, j = right - 1;
          for( ; ; )
          {
              while( a[ ++i ] < pivot ) { }
              while( pivot < a[ --j ] ) { }
              if( i < j )
                  std::swap( a[ i ], a[ j ] );
              else
                  break;
          }
 
          std::swap( a[ i ], a[ right - 1 ] ); 
 
          quicksort1( a, left, i - 1 );
          quicksort1( a, i + 1, right ); 
      }
      else 
          insertionSort( a, left, right );
  }
  
  template <typename Comparable>
  void quickSelect( vector<Comparable> & a, int left, int right, int k )
  {
      if( left + 10 <= right )
      {
         const Comparable & pivot = median3( a, left, right );
 
         int i = left, j = right - 1;
         for( ; ; )
         {
             while( a[ ++i ] < pivot ) { }
             while( pivot < a[ --j ] ) { }
             if( i < j )
                 std::swap( a[ i ], a[ j ] );
             else
                 break;
         }
  
         std::swap( a[ i ], a[ right - 1 ] ); 
 
         if( k <= i )
             quickSelect( a, left, i - 1, k );
         else if( k>i+1)
             quickSelect( a, i + 1, right, k );
      }
      else  
         insertionSort( a, left, right );
  }
  
  template <typename Comparable>
  void insertionSort(std::vector<Comparable>& a, int left, int right)
  {
      for(int insert=left+1; insert<=right; insert++)
      { 
		  Comparable tmp = std::move(a[insert);
		  int k;
          for(k=insert; k>left; k--)
              if(tmp<a(k-1))
			      a[k] = std::move(a[k-1]);
			  else
			      break;
          a[k] = std::move(tmp);
      }
  }
  
  template <typename Comparable>
  void quicksort2( vector<Comparable> & a, int left, int right )
  {
      if( left + 10 <= right )
      {
          const Comparable & pivot = random( a, left, right );
  
          int i = left, j = right - 1;
          for( ; ; )
          {
              while( a[ ++i ] < pivot ) { }
              while( pivot < a[ --j ] ) { }
              if( i < j )
                  std::swap( a[ i ], a[ j ] );
              else
                  break;
          }
 
          std::swap( a[ i ], a[ right - 1 ] ); 
 
          quicksort2( a, left, i - 1 );
          quicksort2( a, i + 1, right ); 
      }
      else 
          insertionSort( a, left, right );
  }
  
  template <typename Comparable>
  const Comparable & random( vector<Comparable> & a, int left, int right)
  {
      srand(time(0));
      int ran=rand()*(right-left+1) + left;
      return a[ran];
  }
